Empirical stability limits for a size-based scheduler applied to Network Utility Maximization

Abstract

Network Utility Maximization (NUM) is an optimization problem that models rate allocation in the Internet. NUM is considered to produce fair bandwidth allocations, an advantage for the implementation of TCP queue management protocols. Prioritization of data packets can benefit from knowing transfer sizes a-priori. A state-of-the-art NUM formulation considers a size-based approach where transmission flows are scaled by some function of a transfer's residual work (inspired by schedulers like Shortest Remaining Processing Time, SRPT). This new NUM-SRPT hybrid scheduler was proven to be stable for a defined region on any arbitrary topology. We found that for all tested topologies, stability limi..